package com.ai.zuochengyun.phase01.class04;

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;

/**
 * 返回所有可能的拼接结果中字典序最小的结果
 */
public class Code01_LowestLexicography {

    public static void main(String[] args) {
        int testTimes = 10000;
        int strLen = 5;
        int arrLen = 6;
        for (int i = 0; i < testTimes; i++) {
            int size = (int) (Math.random() * arrLen) + 1;
            String[] arr = new String[size];
            for (int j = 0; j < arr.length; j++) {
                String str = generateRandomString(strLen);
                arr[j] = str;
            }

            String[] arr1 = new String[size];
            System.arraycopy(arr, 0, arr1, 0, arr.length);
            String s1 = lowestString1(arr1);
            String[] arr2 = new String[size];
            System.arraycopy(arr, 0, arr2, 0, arr.length);
            String s2 = lowestString2(arr2);
            if (!s1.equals(s2)) {
                for (String s : arr) {
                    System.out.print(s + " ");
                }
                System.out.println(s1);
                System.out.println(s2);
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("Finish!");
    }

    /**
     * 生成随机字符串
     *
     * @param strLen
     * @return
     */
    private static String generateRandomString(int strLen) {
        int size = (int) (Math.random() * strLen) + 1;
        char[] arr = new char[size];
        for (int j = 0; j < arr.length; j++) {
            // 大小写随机生成
            int value = (int) (Math.random() * 5);
            arr[j] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
        }
        return String.valueOf(arr);
    }

    private static String lowestString1(String[] arr) {
        if (arr == null || arr.length == 0) {
            return "";
        }
        TreeSet<String> set = process(arr);
        return set.isEmpty() ? "" : set.first();
    }

    /**
     * 所有字符串全排列
     *
     * @param arr
     * @return
     */
    private static TreeSet<String> process(String[] arr) {
        TreeSet<String> ans = new TreeSet<>();
        if (arr.length == 0) {
            return ans;
        }
        for (int i = 0; i < arr.length; i++) {
            // 获取arr的i位置的之后，将其从原始数组中剔除，与其他字符进行全排列
            String first = arr[i];
            String[] nextArr = removeIndexString(arr, i);

            // 将剩余的字符串也进行全排列
            TreeSet<String> treeSet = process(nextArr);
            if (treeSet.isEmpty()) {
                ans.add(first);
            } else {
                for (String cur : treeSet) {
                    ans.add(first + cur);
                }
            }
        }
        return ans;
    }

    private static String[] removeIndexString(String[] arr, int index) {
        String[] ans = new String[arr.length - 1];
        int ansIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i == index) {
                continue;
            }
            ans[ansIndex++] = arr[i];
        }
        return ans;
    }

    private static String lowestString2(String[] arr) {
        if (arr == null || arr.length == 0) {
            return "";
        }
        // 将数组中的字符串排好序后进行拼接
        Arrays.sort(arr, new MyComparator());
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            ans.append(arr[i]);
        }
        return ans.toString();
    }

    private static class MyComparator implements Comparator<String> {

        /**
         * 字典序较小的放前面
         *
         * @param a the first object to be compared.
         * @param b the second object to be compared.
         * @return
         */
        @Override
        public int compare(String a, String b) {
            return (a + b).compareTo(b + a);
        }
    }

}
